package com.yuan.algorithms.分治算法;

import java.util.Arrays;
import java.util.Random;


/**
 * 使用分治思想来实现快速排序
 *
 * 算法步骤
 * 从数列中挑出一个元素，称为 "基准"（pivot）
 * 从右到左、从左到右依次重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。
 * 一轮排序结束后，该基准就处于数列的中间位置。这个称为分区（partition）操作
 * 将基准左边的子序列与右边的子序列递归地重复上述步骤
 *
 * @author YouYuan
 * @date 2022/3/23 9:01
 */
public class QuickSort {

    public static void main(String[] args) {
//        int[] arr = {-5,1,4,5,2,66,2384,-10,222,55,20,-10,3,5};
        int size = 10000000;
        int[] arr = SortUtil.randomArr(size);
        long s = System.currentTimeMillis();
        quickSort(arr);
        long e = System.currentTimeMillis();
        System.out.printf("mergeSort排序耗时：%d(ms)%n", (e-s));
        SortUtil.validateSort(arr);

//        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            // 递归出口，l < 0 || r >= arr.length 因为调用递归的入参保证了这种情况不会出现，所以只要判断l > r即可
            return;
        }
        int left = l;
        int right = r;
        int pivot = arr[left];
        while (left < right) {
            //将右边比pivot小的数据移到左边
            while (left < right && arr[right] >= pivot) {
                right--;
            }
//            swap(arr, left, right);
            if (left < right) {
                arr[left] = arr[right];
            }

            //将左边比pivot大的数据移到右边
            while (left < right && arr[left] <= pivot) {
                left++;
            }
//            swap(arr, left, right);
            if (left < right) {
                arr[right] = arr[left];
            }
            if (left >= right) {
                //一轮排序完成，pivot插入到数列的中间，此时该位置左边所有的元素都比pivot小，右边的所有元素都比pivot大
                arr[left] = pivot;
            }
        }
        //递归排序左边的子序列
        quickSort(arr, l, right-1);
        //递归排序右边的子序列
        quickSort(arr, right+1, r);
    }


}
